1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 package sun.security.util;
27
28 import java.io.ByteArrayOutputStream;
29 import java.util.Arrays;
30
31
32
33
34
35
36
37
38 public class BitArray {
39
40 private byte[] repn;
41 private int length;
42
43 private static final int BITS_PER_UNIT = 8;
44
45 private static int subscript(int idx) {
46 return idx / BITS_PER_UNIT;
47 }
48
49 private static int position(int idx) {
50 return 1 << (BITS_PER_UNIT - 1 - (idx % BITS_PER_UNIT));
51 }
52
53
54
55
56 public BitArray(int length) throws IllegalArgumentException {
57 if (length < 0) {
58 throw new IllegalArgumentException("Negative length for BitArray");
59 }
60
61 this.length = length;
62
63 repn = new byte[(length + BITS_PER_UNIT - 1)/BITS_PER_UNIT];
64 }
65
66
67
68
69
70
71
72
73
74 public BitArray(int length, byte[] a) throws IllegalArgumentException {
75
76 if (length < 0) {
77 throw new IllegalArgumentException("Negative length for BitArray");
78 }
79 if (a.length * BITS_PER_UNIT < length) {
80 throw new IllegalArgumentException("Byte array too short to represent " +
81 "bit array of given length");
82 }
83
84 this.length = length;
85
86 int repLength = ((length + BITS_PER_UNIT - 1)/BITS_PER_UNIT);
87 int unusedBits = repLength*BITS_PER_UNIT - length;
88 byte bitMask = (byte) (0xFF << unusedBits);
89
90
91
92
93
94
95 repn = new byte[repLength];
96 System.arraycopy(a, 0, repn, 0, repLength);
97 if (repLength > 0) {
98 repn[repLength - 1] &= bitMask;
99 }
100 }
101
102
103
104
105
106 public BitArray(boolean[] bits) {
107 length = bits.length;
108 repn = new byte[(length + 7)/8];
109
110 for (int i=0; i < length; i++) {
111 set(i, bits[i]);
112 }
113 }
114
115
116
117
118
119 private BitArray(BitArray ba) {
120 length = ba.length;
121 repn = ba.repn.clone();
122 }
123
124
125
126
127 public boolean get(int index) throws ArrayIndexOutOfBoundsException {
128 if (index < 0 || index >= length) {
129 throw new ArrayIndexOutOfBoundsException(Integer.toString(index));
130 }
131
132 return (repn[subscript(index)] & position(index)) != 0;
133 }
134
135
136
137
138 public void set(int index, boolean value)
139 throws ArrayIndexOutOfBoundsException {
140 if (index < 0 || index >= length) {
141 throw new ArrayIndexOutOfBoundsException(Integer.toString(index));
142 }
143 int idx = subscript(index);
144 int bit = position(index);
145
146 if (value) {
147 repn[idx] |= bit;
148 } else {
149 repn[idx] &= ~bit;
150 }
151 }
152
153
154
155
156 public int length() {
157 return length;
158 }
159
160
161
162
163
164
165
166
167
168
169 public byte[] toByteArray() {
170 return repn.clone();
171 }
172
173 public boolean equals(Object obj) {
174 if (obj == this) return true;
175 if (obj == null || !(obj instanceof BitArray)) return false;
176
177 BitArray ba = (BitArray) obj;
178
179 if (ba.length != length) return false;
180
181 for (int i = 0; i < repn.length; i += 1) {
182 if (repn[i] != ba.repn[i]) return false;
183 }
184 return true;
185 }
186
187
188
189
190 public boolean[] toBooleanArray() {
191 boolean[] bits = new boolean[length];
192
193 for (int i=0; i < length; i++) {
194 bits[i] = get(i);
195 }
196 return bits;
197 }
198
199
200
201
202
203
204 public int hashCode() {
205 int hashCode = 0;
206
207 for (int i = 0; i < repn.length; i++)
208 hashCode = 31*hashCode + repn[i];
209
210 return hashCode ^ length;
211 }
212
213
214 public Object clone() {
215 return new BitArray(this);
216 }
217
218
219 private static final byte[][] NYBBLE = {
220 { (byte)'0',(byte)'0',(byte)'0',(byte)'0'},
221 { (byte)'0',(byte)'0',(byte)'0',(byte)'1'},
222 { (byte)'0',(byte)'0',(byte)'1',(byte)'0'},
223 { (byte)'0',(byte)'0',(byte)'1',(byte)'1'},
224 { (byte)'0',(byte)'1',(byte)'0',(byte)'0'},
225 { (byte)'0',(byte)'1',(byte)'0',(byte)'1'},
226 { (byte)'0',(byte)'1',(byte)'1',(byte)'0'},
227 { (byte)'0',(byte)'1',(byte)'1',(byte)'1'},
228 { (byte)'1',(byte)'0',(byte)'0',(byte)'0'},
229 { (byte)'1',(byte)'0',(byte)'0',(byte)'1'},
230 { (byte)'1',(byte)'0',(byte)'1',(byte)'0'},
231 { (byte)'1',(byte)'0',(byte)'1',(byte)'1'},
232 { (byte)'1',(byte)'1',(byte)'0',(byte)'0'},
233 { (byte)'1',(byte)'1',(byte)'0',(byte)'1'},
234 { (byte)'1',(byte)'1',(byte)'1',(byte)'0'},
235 { (byte)'1',(byte)'1',(byte)'1',(byte)'1'}
236 };
237
238 private static final int BYTES_PER_LINE = 8;
239
240
241
242
243 public String toString() {
244 ByteArrayOutputStream out = new ByteArrayOutputStream();
245
246 for (int i = 0; i < repn.length - 1; i++) {
247 out.write(NYBBLE[(repn[i] >> 4) & 0x0F], 0, 4);
248 out.write(NYBBLE[repn[i] & 0x0F], 0, 4);
249
250 if (i % BYTES_PER_LINE == BYTES_PER_LINE - 1) {
251 out.write('\n');
252 } else {
253 out.write(' ');
254 }
255 }
256
257
258 for (int i = BITS_PER_UNIT * (repn.length - 1); i < length; i++) {
259 out.write(get(i) ? '1' : '0');
260 }
261
262 return new String(out.toByteArray());
263
264 }
265
266 public BitArray truncate() {
267 for (int i=length-1; i>=0; i--) {
268 if (get(i)) {
269 return new BitArray(i+1, Arrays.copyOf(repn, (i + BITS_PER_UNIT)/BITS_PER_UNIT));
270 }
271 }
272 return new BitArray(1);
273 }
274
275 }